package practice17;

public class Main {
    public static int solution(int[] array) {
        int count = 0;
        Integer candidate = null;

        // 遍历数组寻找候选元素
        for (int num : array) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        // 因为题目保证一定存在这样的元素，这里不需要再验证candidate是否真的超过了一半
        return candidate;
    }

    public static void main(String[] args) {
        // 测试用例
        System.out.println(solution(new int[]{1, 3, 8, 2, 3, 1, 3, 3, 3})); // 输出：3
        System.out.println(solution(new int[]{5, 5, 5, 1, 2, 5, 5}));       // 输出：5
        System.out.println(solution(new int[]{9, 9, 9, 9, 8, 9, 8, 8}));    // 输出：9
    }
}